package com.dy.图.最短路径;

import com.sun.corba.se.impl.orbutil.graph.Graph;

public class ShotestPath {
    //dijkstra算法类似prime算法
    public static void dijkstra(int[][] G, int v[], int start,int end) {
        //用于记录和各顶点的最小距离
        int mindist[] = new int[v.length];

        boolean finish[] = new boolean[v.length];
        //用于记录前驱节点
        int[] prenode = new int[v.length];

        for (int i = 0; i < v.length; i++) {
            finish[i] = false;
            mindist[i] = G[start][i];
            prenode[i] = start;
        }
        //该节点已经完成
        finish[start] = true;
        //需要依次添加n-1个节点
        for (int i = 1; i < v.length; i++) {

            int min = Integer.MAX_VALUE;
            int k = 0;

            //先找数组里面最小的
            for (int j = 0; j < v.length; j++) {
                if (!finish[j] && min > mindist[j]) {
                    min = mindist[j];
                    k = j;
                }
            }
            finish[k] = true;

            for (int j = 0; j < v.length; j++) {
                if (!finish[j] && ((min + G[k][j]) < mindist[j])) {
                    mindist[j] = min + G[k][j];
                    prenode[j] = k;
                }
            }
        }
//        for (int i = 0; i < v.length; i++) {
//            System.out.println("v" + start + "...v" + prenode[i] + "->v" + i + ", s=" + mindist[i]);
//        }

        //   }
        findPath(start, prenode, mindist,end);
    }

    static void findPath(int start, int[] prenode, int[] mindist,int end) {
        if(end==start){
            return;
        }
        findPath(start,prenode,mindist,prenode[end]);
        System.out.println(prenode[end]+">>>>>>>>>>"+end+",一共走了"+mindist[end]+"步");
    }
        private static int N = 1000;
        private static int[][] Graph = {
                {0, 1, 5, N, N, N, N, N, N},
                {1, 0, 3, 7, 5, N, N, N, N},
                {5, 3, 0, N, 1, 7, N, N, N},
                {N, 7, N, 0, 2, N, 3, N, N},
                {N, 5, 1, 2, 0, 3, 6, 9, N},
                {N, N, 7, N, 3, 0, N, 5, N},
                {N, N, N, 3, 6, N, 0, 2, 7},
                {N, N, N, N, 9, 5, 2, 0, 4},
                {N, N, N, N, N, N, 7, 4, 0}};

        public static void main (String[]args){
            int[] v = {0, 1, 2, 3, 4, 5, 6, 7, 8};
            dijkstra(Graph, v, 8,0);
        }
    }
